package cn.suchan.jianzhi.q39_tree;

/**
 * 知识点：平衡二叉树
 * 题目描述
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 * <p>
 * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 * </p>
 *
 * @author suchan
 * @date 2019/06/04
 */
public class Solution {

    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 分别获取根节点的左子树和右子树的深度（最长路径节点数）
        int left = depth(root.left);
        int right = depth(root.right);

        // 如果左右子树相差大于1，则不是平衡二叉树
        if (Math.abs(left - right) > 1) {
            return false;
        }
        return true;

    }

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 这里得到的是该节点的子节点个数
        int left = depth(root.left) + 1;
        int right = depth(root.right) + 1;

        // 返回比较大的那个数
        return Math.max(left, right);

        /*int left = depth(root.left);
        int right = depth(root.right);
        // 返回比较大的那个数
        return left > right ? (left + 1) : (right + 1);*/
    }

    /**
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution2(TreeNode root) {
        return etDepth(root) != -1;
    }

    private int etDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = etDepth(root.left);
        if (left == -1) {
            return -1;
        }
        int right = etDepth(root.right);
        if (right == -1) {
            return -1;
        }
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.left = node8;
        node5.right = node9;
        node9.right = node10;

        Solution solution = new Solution();
        System.out.println(solution.IsBalanced_Solution(node1));
    }
}
